Every day, countless data packets are transmitted from one computer to another within computer networks. Each data packet contains a source IP address, which is the where the data packet originated. Each data packet also contains a destination IP address, which is the ultimate destination for the data packet. Both IP addresses are a series of numbers separated by decimals, such as 172.168.4.2. A firewall uses the IP addresses to determine whether to permit a data packet to pass through the firewall. A computer network may have dozens of firewalls, each designed to permit or deny certain types of data packets. Because of the large quantity of data packets processed by each firewall, even small improvements in the processing time per data packet can have significant improvements in the overall efficiency of a single firewall, and thus, the computer network as a whole. Similarly, because Internet routers also use IP address filtering as a method for routing data packets, an increase in router efficiency can be realized by an improvement in filtering efficiency. Therefore, a need exists for an improved method for filtering data packet IP addresses.
One portion of the IP address filtering process is determining whether the incoming IP address is present in a list of IP addresses. Firewalls can have exclusion lists and/or inclusion lists. In other words, when a firewall receives a data packet, the firewall may determine whether the data packet source IP address is present in a list of allowable data packet IP addresses, determine if the source IP address is present in a list of prohibited data packet IP addresses, or a combination of the two. If the IP address is present in the list of allowable IP addresses and not in the list of prohibited IP addresses, the firewall permits the data packet to pass through the firewall. Otherwise, the firewall denies the data packet passage past the firewall. Thus, the firewall must determine whether an incoming numbered list (i.e. a destination IP address) is present in a numbered list data set (i.e. a list of IP addresses), regardless of whether the numbered list data set is allowable or prohibited numbered lists. For example, the firewall determines whether the incoming numbered list 1.3.2.4 is present in the numbered list data set 1.2.3.4, 1.4.3.2, 1.2.2.2, 1.3.2.4, and 4.2.3.6. The prior art method for determining whether the incoming numbered list is present in a numbered list data set is to create a tree containing all of the numbered lists in the numbered list data set. An example of a prior art tree for the numbered list data set above is illustrated in FIG. 1. In the prior art tree, each level represents a number position. At each level, the firewall makes a determination whether the incoming numbered list matches any of the numbers at that level. If the incoming numbered list matches a number in the tree, then the firewall proceeds to the next level. If the incoming numbered list does not match a number, the incoming numbered list is not present in the numbered list data set. The comparison process continues until the firewall reaches the last level of the tree. Thus, by comparing an incoming numbered list to the tree, a firewall can determine whether an incoming numbered list is present in the numbered list data set.
One of the problems with the tree method for determining whether an incoming numbered list is present in a numbered list data set is that any of the numbered lists from the numbered list data set may contain a wildcard character. A wildcard character is a keyboard character that can be used to represent one or many characters. For example, the asterisk (*) typically represents one or more characters and the question mark (?) typically represents a single character. When a numbered list from the numbered list data set contains a wildcard character, there is at least one level of recursion in the process of determining whether an incoming numbered list is present in the numbered list data set. In other words, at each level in the tree, the firewall must make two determinations: whether any of the nodes represent a wildcard and whether the incoming numbered list matches any of the nodes. If a level contains a matching node and a wildcard node, then the firewall must traverse two paths down from that level. The presence of a wildcard at a lower level would create even more paths for the firewall to trace. Thus, wildcards in the tree lead to an increasing amount of computational steps and an undesirable increase in the time required to determine whether an incoming numbered list is present in a numbered list data set.
Consequently, a need exists in the art for an improved method for determining whether an incoming numbered list is present in a numbered list data set. Moreover, a need exists in the art for a method for determining whether an incoming numbered list is present in a numbered list data set that does not require extra computational steps when the numbered list data set contains a wildcard character. Finally, a need exists for a method for determining whether an incoming numbered list is present in a numbered list data set in which the method eliminates the need for recursive computational sets.